package leecode;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 第十六天 排序
 */
public class LeetCode16 {

    //第二题，利用快排进行排序
//    若拼接字符串 x + y > y + x，则 x “大于” y ；
//    反之，若 x + y < y + x ，则 x “小于” y ；
    public static int sort(String[] str,int left,int right){
        int l=left;
        int r=right;
        String tmp=str[l];
        //    若拼接字符串 x + y > y + x，则 x “大于” y ；
        //    反之，若 x + y < y + x ，则 x “小于” y ；
        //  利用这样的规则来调整快排的规则
        while (l<r){
            while (l<r&&(tmp+str[r]).compareTo(str[r]+tmp)<=0){
                r--;
            }
            str[l]=str[r];
            while (l<r&&(tmp+str[l]).compareTo(str[l]+tmp)>=0){
                l++;
            }
            str[r]=str[l];
        }
        str[l]=tmp;
        return l;
    }
    //快速排序
    public void fast_sort(String[]str,int l,int r){
        if(r<=l){
            return;
        }
//        进行分治递归
        int k=sort(str,l,r);
        fast_sort(str,l,k);
        fast_sort(str,k+1,r);
    }

    public String minNumber(int[] nums) {
        //转换为字符，为后面的拼接提供条件
        String[] strings=new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strings[i]=String.valueOf(nums[i]);
        }
        fast_sort(strings,0,nums.length-1);
        StringBuilder res = new StringBuilder();
        for(String s : strings)
            res.append(s);
        return res.toString();

    }


    //第一题
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int i=0;
        int count=0;
        while (nums[i]==0){
            count++;
            i++;
        }
        for (int j = i; j <nums.length-1; j++) {
            if(nums[j]!=nums[j+1]-1){
                count--;
                nums[j]=nums[j]+1;
                j--;
            }
            if(count<0){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        LeetCode16 leetCode16=new LeetCode16();
        int []arr={1,2,3,1};
        leetCode16.minNumber(arr);
    }
}
